package main

// 20. 有效的括号
func main() {
	str := "([)]"
	res := isValid(str)
	println(res)
}

var StrMap = map[string]string{
	")": "(",
	"]": "[",
	"}": "{",
}

func isValid(s string) bool {
	// 使用栈来求解
	var stack []string

	for i := range s {
		u := string(s[i])
		if mapVal, has := StrMap[u]; has {
			// 消消乐
			if len(stack) == 0 {
				return false
			}
			if stack[len(stack)-1] == mapVal {
				stack = stack[:len(stack)-1]
			} else {
				return false
			}
		} else {
			stack = append(stack, u)
		}
	}

	return len(stack) == 0
}

//func isValid(s string) bool {   解答错误
//	var StrMap = map[string]string{
//		")": "(",
//		"]": "[",
//		"}": "{",
//	}
//
//	var StrSet = map[string]int{
//		"(": 0,
//		"[": 0,
//		"{": 0,
//	}
//
//	for i := range s {
//		u := s[i]
//		if _, has := StrSet[string(u)]; has {
//			StrSet[string(u)] = StrSet[string(u)] + 1
//		}
//		if mapStr, has := StrMap[string(u)]; has {
//			StrSet[mapStr] = StrSet[mapStr] - 1
//			if StrSet[mapStr] < 0 {
//				return false
//			}
//		}
//	}
//
//	for _, value := range StrSet {
//		if value != 0 {
//			return false
//		}
//	}
//
//	return true
//}

// 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
//
//有效字符串需满足：
//
//左括号必须用相同类型的右括号闭合。
//左括号必须以正确的顺序闭合。
//每个右括号都有一个对应的相同类型的左括号。
//
//
//示例 1：
//
//输入：s = "()"
//输出：true
//示例 2：
//
//输入：s = "()[]{}"
//输出：true
//示例 3：
//
//输入：s = "(]"
//输出：false
//
//
//提示：
//
//1 <= s.length <= 104
//s 仅由括号 '()[]{}' 组成
